/* Changes:
 *
 * printSegment replaced with toString
 *   this is a cleaner, more flexible and correct way to print custom classes
 */
package gss;

import org.apache.commons.math.fraction.BigFraction;
import static org.apache.commons.math.fraction.BigFraction.ONE;
import static org.apache.commons.math.fraction.BigFraction.ONE_HALF;
import static org.apache.commons.math.fraction.BigFraction.ZERO;

import java.util.Vector;

/**
 *
 * @author mdm32
 */
public class LineSegment {

    private String lName;
    private BigFraction X1;
    private BigFraction Y1;
    private BigFraction X2;
    private BigFraction Y2;

    //constructors
    public LineSegment() {
        lName = "0";
        X1 = new BigFraction(0);
        Y1 = new BigFraction(0);
        X2 = new BigFraction(1);
        Y2 = new BigFraction(1);
    }

    public LineSegment(String name, BigFraction x1, BigFraction y1,
            BigFraction x2, BigFraction y2) {
        lName = name;
        X1 = x1;
        Y1 = y1;
        X2 = x2;
        Y2 = y2;
    }

    public LineSegment(String name, double x1, double y1,
            double x2, double y2) {
        lName = name;
        X1 = new BigFraction(x1);
        Y1 = new BigFraction(y1);
        X2 = new BigFraction(x2);
        Y2 = new BigFraction(y2);
    }

    public LineSegment(Vertex a, Vertex b) {
        lName = "";
        X1 = a.getX();
        Y1 = a.getY();
        X2 = b.getX();
        Y2 = b.getY();
    }

    public LineSegment(String name, Vertex a, Vertex b) {
        lName = name;
        X1 = a.getX();
        Y1 = a.getY();
        X2 = b.getX();
        Y2 = b.getY();
    }

    //recover data
    public String getName() {
        return lName;
    }

    public BigFraction getX1() {
        return X1;
    }

    public BigFraction getX2() {
        return X2;
    }

    public BigFraction getY1() {
        return Y1;
    }

    public BigFraction getY2() {
        return Y2;
    }

    public Vertex getVertex1() {
        return new Vertex(X1, Y1);
    }

    public Vertex getVertex2() {
        return new Vertex(X2, Y2);
    }

    //set data
    public void setName(String s) {
        lName = s;
    }

    public void setX1(BigFraction x1) {
        X1 = x1;
    }

    public void setX2(BigFraction x2) {
        X2 = x2;
    }

    public void setY1(BigFraction y1) {
        Y1 = y1;
    }

    public void setY2(BigFraction y2) {
        Y2 = y2;
    }

    /* Returns the approximate length of the segment
     * as a double value
     */
    public double segmentLength() {
        BigFraction cy = Y2.subtract(Y1);
        BigFraction cx = X2.subtract(X1);
        return Math.sqrt(((cx.multiply(cx)).add(cy.multiply(cy))).doubleValue());
    }

    /*Returns a string:
     * name (x1,y1), (x2,y2)
     */
    @Override
    public String toString() {
        return (lName + " (" + X1 + "," + Y1 +
                "), (" + X2 + "," + Y2 + ")");
    }

    /*returns true if the segment is vertical
     */
    public boolean isNotVertical() {
        if (X1.equals(X2)) {
            return false;
        }
        return true;
    }

    /*returns the y evaluation at x
     */
    public BigFraction yValue(BigFraction x) {
        if (isNotVertical()) {
            //(Y2-Y1)*x/(X2-X1)+Y1-(X1*(Y2-Y1)/(X2-X1))
            return (Y2.subtract(Y1)).multiply(x.divide(X2.subtract(X1))).add(Y1.subtract(X1.multiply(Y2.subtract(Y1)).divide(X2.subtract(X1))));
        } else {
            if (x.equals(X1)) {
                return Y1;
            } else {
                return null;
            }
        }
    }

    /*returns the slope if not infinite
     * otherwise it returns BigFraction(0) as if horizontal
     */
    public BigFraction slope() {
        if (isNotVertical()) {
            return (Y2.subtract(Y1)).divide(X2.subtract(X1));
        } else {
            return new BigFraction(0);
        }
    }

    //overrides objects equals method
    @Override
    public boolean equals(Object b) {
        boolean first = (b != null) && (b.getClass() == this.getClass()) && (this.getName().equals(((LineSegment) b).getName()));
        boolean seconda = this.getX1().equals(((LineSegment) b).getX1()) && this.getY1().equals(((LineSegment) b).getY1()) && this.getX2().equals(((LineSegment) b).getX2()) && this.getY2().equals(((LineSegment) b).getY2());
        boolean secondb = this.getX1().equals(((LineSegment) b).getX2()) && this.getY1().equals(((LineSegment) b).getY2()) && this.getX2().equals(((LineSegment) b).getX1()) && this.getY2().equals(((LineSegment) b).getY1());
        return first && (seconda || secondb);
    }

    @Override
    public int hashCode() {
        int hash = 3;
        hash = 79 * hash + (this.lName != null ? this.lName.hashCode() : 0);
        hash = 79 * hash + (this.X1 != null ? this.X1.hashCode() : 0);
        hash = 79 * hash + (this.Y1 != null ? this.Y1.hashCode() : 0);
        hash = 79 * hash + (this.X2 != null ? this.X2.hashCode() : 0);
        hash = 79 * hash + (this.Y2 != null ? this.Y2.hashCode() : 0);
        return hash;
    }

    /*Calculates the coordinates where lines corresponding to
     * segments this and b intersect
     * returns a vertex with this BigFraction coordinate.
     *
     */
    public Vertex intersection(LineSegment b) {
        BigFraction x = new BigFraction(0);
        BigFraction y = new BigFraction(0);

        BigFraction x1 = X1;
        BigFraction y1 = Y1;
        BigFraction x2 = X2;
        BigFraction y2 = Y2;
        BigFraction x3 = b.getX1();
        BigFraction y3 = b.getY1();
        BigFraction x4 = b.getX2();
        BigFraction y4 = b.getY2();


        Vector<String> segs = new Vector<String>();
        segs.add(lName);
        segs.add(b.getName());


        if (x1.equals(x2)) {
            if (x3.equals(x4)) {
                if (yValue(x3).equals(y1)) {
                    return new Vertex(segs, x3, y1);
                } else if (yValue(x3).equals(y2)) {
                    return new Vertex(segs, x3, y2);
                } else if (yValue(x4).equals(y1)) {
                    return new Vertex(segs, x4, y1);
                } else if (yValue(x4).equals(y2)) {
                    return new Vertex(segs, x4, y2);
                } else {
                    if (y4.compareTo(y3) >= 0) {
                        return new Vertex(segs, x1, y3);
                    } else {
                        return new Vertex(segs, x4, y4);
                    }
                }
            }
            x = x1;
            BigFraction s2 = (y4.subtract(y3)).divide(x4.subtract(x3));
            y = s2.multiply(x.subtract(x3)).add(y3);
        } else if (x3.equals(x4)) {
            x = x3;
            BigFraction s1 = (y2.subtract(y1)).divide(x2.subtract(x1));
            y = s1.multiply(x.subtract(x1)).add(y1);
        } else {
            BigFraction s1 = (y2.subtract(y1)).divide(x2.subtract(x1));
            BigFraction s2 = (y4.subtract(y3)).divide(x4.subtract(x3));
            //x = (x1*(x4*(y3-y2)+x3*(y2-y4))+x2*(x4*(y1-y3)+x3*(y4-y1)))/(-(x3-x4)*(y1-y2)+(x1-x2)*(y3-y4));
            x = (x1.multiply(x4.multiply(y3.subtract(y2)).add(x3.multiply(y2.subtract(y4)))).add(x2.multiply(x4.multiply(y1.subtract(y3)).add(x3.multiply(y4.subtract(y1)))))).divide(((x4.subtract(x3)).multiply(y1.subtract(y2)).add((x1.subtract(x2)).multiply(y3.subtract(y4)))));
            //y = s1*(x-x1)+y1;
            y = s1.multiply(x.subtract(x1)).add(y1);

        }

        return new Vertex(segs, x, y);
    }

    /*checks if segments this and b intersect
     * returns true if an intersection exists
     */
    public boolean intersects(LineSegment b) {
        BigFraction x1 = X1;
        BigFraction y1 = Y1;
        BigFraction x2 = X2;
        BigFraction y2 = Y2;
        BigFraction x3 = b.getX1();
        BigFraction y3 = b.getY1();
        BigFraction x4 = b.getX2();
        BigFraction y4 = b.getY2();

        if (isNotVertical()) {
            if (yValue(x3).equals(y3)) {
                if ((x1.compareTo(x3) <= 0 && x2.compareTo(x3) >= 0) || ((x1.compareTo(x3) >= 0 && x2.compareTo(x3) <= 0))) {
                    return true;
                }
            }

            if (yValue(x4).equals(y4)) {
                if ((x1.compareTo(x4) <= 0 && x2.compareTo(x4) >= 0) || ((x1.compareTo(x4) >= 0 && x2.compareTo(x4) <= 0))) {
                    return true;
                }
            }
            if(b.isNotVertical()){
                if (b.yValue(x1).equals(y1)) {
                    if ((x3.compareTo(x1) <= 0 && x4.compareTo(x1) >= 0) || ((x3.compareTo(x1) >= 0 && x4.compareTo(x1) <= 0))) {
                        return true;
                    }
                }
                if (b.yValue(x2).equals(y2)) {
                    if ((x3.compareTo(x2) <= 0 && x4.compareTo(x2) >= 0) || ((x3.compareTo(x2) >= 0 && x4.compareTo(x2) <= 0))) {
                        return true;
                    }
                }
            }

            if (isColinearTo(b)) {
                if (((x3.compareTo(x2) <= 0 && x4.compareTo(x2) >= 0) || ((x3.compareTo(x2) >= 0 && x4.compareTo(x2) <= 0))) || ((x3.compareTo(x1) <= 0 && x4.compareTo(x1) >= 0) || ((x3.compareTo(x1) >= 0 && x4.compareTo(x1) <= 0))) || ((x1.compareTo(x3) <= 0 && x2.compareTo(x3) >= 0) || ((x1.compareTo(x3) >= 0 && x2.compareTo(x3) <= 0))) || ((x1.compareTo(x4) <= 0 && x2.compareTo(x4) >= 0) || ((x1.compareTo(x4) >= 0 && x2.compareTo(x4) <= 0)))) {
                    return true;
                }
            } else {


                //double det123 = (x2 - x1)*(y3 - y1) - (x3 - x1)*(y2 - y1);
                BigFraction det123 = ((x2.subtract(x1)).multiply(y3.subtract(y1))).subtract((x3.subtract(x1)).multiply(y2.subtract(y1)));
                //double det124 = (x2 - x1)*(y4 - y1) - (x4 - x1)*(y2 - y1);
                BigFraction det124 = ((x2.subtract(x1)).multiply(y4.subtract(y1))).subtract((x4.subtract(x1)).multiply(y2.subtract(y1)));
                //double det341 = (x3 - x1)*(y4 - y1) - (x4 - x1)*(y3 - y1);
                BigFraction det341 = ((x3.subtract(x1)).multiply(y4.subtract(y1))).subtract((x4.subtract(x1)).multiply(y3.subtract(y1)));

                BigFraction det342 = det123.subtract(det124).add(det341);

                BigFraction zero = new BigFraction(0);

                if ((det123.multiply(det124)).compareTo(zero) == -1 && (det341.multiply(det342)).compareTo(zero) == -1) {
                    return true;
                }
                if ((det123.multiply(det124)).equals(zero) && (det341.multiply(det342)).equals(zero)) {
                    return true;
                }
            }
        } else {
            if ((x3.compareTo(x1) <= 0 && x4.compareTo(x1) >= 0) || (x3.compareTo(x1) >= 0 && x4.compareTo(x1) <= 0)) {
                if (b.isNotVertical()) {
                    if ((y1.compareTo(b.yValue(x1)) <= 0 && y2.compareTo(b.yValue(x1)) >= 0) || (y1.compareTo(b.yValue(x1)) >= 0 && y2.compareTo(b.yValue(x1)) <= 0)) {
                        return true;
                    }
                } else {
                    if (((y3.compareTo(y2) <= 0 && y4.compareTo(y2) >= 0) || ((y3.compareTo(y2) >= 0 && y4.compareTo(y2) <= 0))) || ((y3.compareTo(y1) <= 0 && y4.compareTo(y1) >= 0) || ((y3.compareTo(y1) >= 0 && y4.compareTo(y1) <= 0))) || ((y1.compareTo(y3) <= 0 && y2.compareTo(y3) >= 0) || ((y1.compareTo(y3) >= 0 && y2.compareTo(y3) <= 0))) || ((y1.compareTo(y4) <= 0 && y2.compareTo(y4) >= 0) || ((y1.compareTo(y4) >= 0 && y2.compareTo(y4) <= 0)))) {
                        return true;
                    }
                }

            }
        }

        return false;
    }

    /**
     * Tests if segments this and b are parallel. For the math behind
     * this see the comments for the determinant() function.
     */
    public boolean isParallelTo(LineSegment b) {
        return determinant(b).equals(ZERO);
    }

    /**
     * T ests if segments this and b are collinear. For the math behind
     * this see the comments for the determinant() function.
     */
    public boolean isColinearTo(LineSegment b) {
        // first check parallel, then use segment P1-P3 to check collinear
        return this.isParallelTo(b) && this.isParallelTo(
                new LineSegment(this.getVertex1(), b.getVertex1()));
    }

    /**
     * Calculates intersection point of 2 line segments. For the math
     * see comment to determinant().
     * REQ: this is NOT parallel to b
     * @param   other	the other LineSegment
     * @return  the intersection of this and other if it exists, 
     *	    null otherwise.
     */
    public Vertex intersectionPoint(LineSegment b) {
        LineSegment c = new LineSegment(this.getVertex1(), b.getVertex1());

        BigFraction denom = this.determinant(b);
        BigFraction num_sa = c.determinant(b);
        BigFraction num_tb = c.determinant(this);

        BigFraction sa = num_sa.divide(denom);
        BigFraction tb = num_tb.divide(denom);

        /* in range if 0 <= sa, tb <= 1
         * -.5 <= sa, tb - .5 <= .5
         * |sa,tx - .5| <= .5
         * return null if out of range: |sa,tx - .5| > .5
         */
        if (sa.subtract(ONE_HALF).abs().compareTo(ONE_HALF) > 0 || tb.subtract(ONE_HALF).abs().compareTo(ONE_HALF) > 0) {
            return null;
        }
        // else, intersection exists

        // x = (1-sa)*X1+sa*X2 = X1 + sa(X2-X1)
        BigFraction x = this.X1.add(sa.multiply(this.X2.subtract(this.X1)));

        // y = (1-sa)*Y1+sa*Y2 = Y1 + sa(Y2-Y1)
        BigFraction y = this.Y1.add(sa.multiply(this.Y2.subtract(this.Y1)));

        Vector<String> visibility = new Vector<String>();
        visibility.add(this.lName);
        visibility.add(b.lName);

        return new Vertex(visibility, x, y);
    }

    /* Extends the line segment:
     * from end point 1 or 2 (endpoint)
     * to some integer endpoint within the given window [xmin,xmax],[ymin,ymax]
     * It is required that the segment is properly contained in this window
     */
    public LineSegment extend(int endpoint, int xmin, int ymin, int xmax, int ymax) {
        String name = "extended";

        LineSegment bottom = new LineSegment("bottom", new BigFraction(xmin), new BigFraction(ymin),
                new BigFraction(xmax), new BigFraction(ymin));
        LineSegment left = new LineSegment("left", new BigFraction(xmin), new BigFraction(ymin),
                new BigFraction(xmin), new BigFraction(ymax));
        LineSegment right = new LineSegment("right", new BigFraction(xmax), new BigFraction(ymin),
                new BigFraction(xmax), new BigFraction(ymax));
        LineSegment top = new LineSegment("top", new BigFraction(xmin), new BigFraction(ymax),
                new BigFraction(xmax), new BigFraction(ymax));


        Vertex bvert = intersection(bottom);
        Vertex lvert = intersection(left);
        Vertex rvert = intersection(right);
        Vertex tvert = intersection(top);

        Vector<Vertex> validvertices = new Vector<Vertex>();
        if (xmin <= bvert.getX().doubleValue() && bvert.getX().doubleValue() <= xmax && ymin <= bvert.getY().doubleValue() && bvert.getY().doubleValue() <= ymax) {
            if (intersects(bottom)) {
                validvertices.add(bvert);
            }
        }
        if (xmin <= lvert.getX().doubleValue() && lvert.getX().doubleValue() <= xmax && ymin <= lvert.getY().doubleValue() && lvert.getY().doubleValue() <= ymax) {
            if (intersects(left)) {
                validvertices.add(lvert);
            }
        }
        if (xmin <= rvert.getX().doubleValue() && rvert.getX().doubleValue() <= xmax && ymin <= rvert.getY().doubleValue() && rvert.getY().doubleValue() <= ymax) {
            if (intersects(right)) {
                validvertices.add(rvert);
            }
        }
        if (xmin <= tvert.getX().doubleValue() && tvert.getX().doubleValue() <= xmax && ymin <= tvert.getY().doubleValue() && tvert.getY().doubleValue() <= ymax) {
            if (intersects(top)) {
                validvertices.add(tvert);
            }
        }

        Vertex endpt = new Vertex();
        if (endpoint == 1) {
            endpt.setX(X2);
            endpt.setY(Y2);
        } else if (endpoint == 2) {
            endpt.setX(X1);
            endpt.setY(Y1);
        }

        Vertex critical = bvert;
        if (critical.distanceTo(endpt) > lvert.distanceTo(endpt)) {
            critical = lvert;
        }
        if (critical.distanceTo(endpt) > rvert.distanceTo(endpt)) {
            critical = rvert;
        }
        if (critical.distanceTo(endpt) > tvert.distanceTo(endpt)) {
            critical = tvert;
        }

        LineSegment newEndPtSpace = new LineSegment("endpt_space", endpt, critical);

        double xbegin = 0;
        double xend = 0;
        double ybegin = 0;
        double yend = 0;

        BigFraction randx = new BigFraction(0);
        BigFraction randy = new BigFraction(0);

        if (isNotVertical()) {
            if (endpt.getX().compareTo(critical.getX()) == -1) {
                xbegin = endpt.getX().doubleValue();
                xend = critical.getX().doubleValue();
            } else {
                xend = endpt.getX().doubleValue();
                xbegin = critical.getX().doubleValue();
            }

            double rand = (Math.random() * (xend - xbegin) + xbegin);
            int randi = (int) rand * 1000;
            double randd = (double) randi / 1000;
            randx = new BigFraction(randd);
            randy = yValue(randx);
        } else {
            randx = X1;
            if (endpt.getY().compareTo(critical.getY()) == -1) {
                ybegin = endpt.getY().doubleValue();
                yend = critical.getY().doubleValue();
            } else {
                yend = endpt.getY().doubleValue();
                ybegin = critical.getY().doubleValue();
            }
            double rand = (Math.random() * (yend - ybegin) + ybegin);
            int randi = (int) rand * 1000;
            double randd = (double) randi / 1000;
            randy = new BigFraction(randd);
        }

        LineSegment rsegment = new LineSegment();
        if (endpoint == 1) {
            rsegment = new LineSegment(lName, randx, randy, endpt.getX(), endpt.getY());
        } else if (endpoint == 2) {
            rsegment = new LineSegment(lName, endpt.getX(), endpt.getY(), randx, randy);
        }

        return rsegment;
    }

    /**
     * Calculates determinant of the 2x2 matrix [ [dX1 dY1] [dX2 dY2] ]. 
     * The resulting value is useful in many ways: if 0, then the 2 segments
     * are parallel. If nonzero it can be used for calculating intersections.
     * For the math behind this see:
     * http://local.wasp.uwa.edu.au/~pbourke/geometry/lineline2d/
     * @param	l	the other LineSegment
     * @return	a determinant of the 2x2 matrix [ [dX1 dY1] [dX2 dY2] ] 
     */
    private BigFraction determinant(LineSegment l) {
        BigFraction dX1 = X2.subtract(X1);
        BigFraction dX2 = l.X2.subtract(l.X1);
        BigFraction dY1 = Y2.subtract(Y1);
        BigFraction dY2 = l.Y2.subtract(l.Y1);

        /* | dX1   dY1 |
         * |           | = dX1 * dY2 - dX2 * dY1
         * | dX2   dY2 |
         */
        return dX1.multiply(dY2).subtract(dX2.multiply(dY1));
    }

    /* Tests if this segment intersects segment b
     */
    public boolean overlaps(LineSegment b) {
        if (isParallelTo(b) && intersects(b)) {
            return true;
        }
        return false;
    }
}